<?php
/**
 * Created by PhpStorm.
 * User: allen
 * Date: 2019/2/19
 * Time: 10:30 PM
 */

/**
 * 递归实现
 * @param $list
 * @param $item
 * @return bool
 */
function binary_search($list, $item)
{
    $count = count($list);

    if ($count > 0) {
        $mid = (int)($count / 2);

        if ($list[$mid] == $item) {
            return true;
        } elseif ($item < $list[$mid]) {
            return binary_search(array_slice($list, 0, $mid), $item);
        } elseif ($item > $list[$mid]) {
            return binary_search(array_slice($list, $mid + 1), $item);
        }
    } else {
        return false;
    }
}

/**
 * 迭代方式实现
 * @param $list
 * @param $item
 * @return bool
 */
function binary_search1($list, $item)
{
    $count = count($list);
    $mid = (int)$count / 2;
    while ($mid > 0) {
        if ($list[$mid] == $item) {
            return true;
        } elseif ($list[$mid] > $item) {
            $list = array_slice($list, 0, $mid);
        } elseif ($list[$mid] < $item) {
            $list = array_slice($list, $mid + 1);
        }

        $count = count($list);
        $mid = (int)$count / 2;
    }
    return false;
}


$list = [17, 20, 36, 44, 44,55, 79, 100];
sort($list);
var_dump(binary_search($list, 36));

//var_dump(binary_search($list, 79));

var_dump(binary_search1($list,44));